import java.util.Random;

class Solution {
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public int qsort(int[] nums, int l, int r, int k) {
        if (l == r)return nums[l];
        int left = l - 1;
        int right = r + 1;
        int i = l;
        int key = nums[new Random().nextInt(r - l + 1) + l];
        while (i < right) {
            if (nums[i] < key)
                swap(nums, ++left, i++);
            else if (nums[i] > key)
                swap(nums, --right, i);
            else
                i++;
        }
        int b = right - left - 1;
        int c = r - right + 1;
        if (c >= k)
            return qsort(nums, right, r, k);
        else if (b + c >= k)
            return key;
        else
            return qsort(nums, l, left, k - b - c);
    }

//    public int qsort(int[] nums, int l, int r, int k) {
//        if (l == r)return nums[l];
//        int left = l - 1;
//        int right = r + 1;
//        int i = l;
//        int key = nums[new Random().nextInt(r - l + 1) + l];
//        while (i < right) {
//            if (nums[i] < key)
//                swap(nums, ++left, i++);
//            else if (nums[i] > key)
//                swap(nums, --right, i);
//            else
//                i++;
//        }
//        int b = right - left - 1;
//        int c = r - right + 1;
//        if (c >= k)
//            return qsort(nums, right, r, k);
//        else if (b + c >= k)
//            return key;
//        else
//            return qsort(nums, l, left, k - b - c);
//    }

    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }

    public static void main(String[] args) {

    }
}